package heap.simple;

import java.util.PriorityQueue;

/**
 * 示例：
 *
 * 输入：
 * ["KthLargest", "add", "add", "add", "add", "add"]
 * [[3, [4, 5, 8, 2]], [3], [5], [10], [9], [4]]
 * 输出：
 * [null, 4, 5, 5, 8, 8]
 *
 * 解释：
 * KthLargest kthLargest = new KthLargest(3, [4, 5, 8, 2]);
 * kthLargest.add(3);   // return 4
 * kthLargest.add(5);   // return 5
 * kthLargest.add(10);  // return 5
 * kthLargest.add(9);   // return 8
 * kthLargest.add(4);   // return 8
 * 链接：https://leetcode-cn.com/problems/kth-largest-element-in-a-stream
 */
public class KthLargestElementInAStream {

    PriorityQueue<Integer> minHeap = new PriorityQueue<>();
    int k;
    public KthLargestElementInAStream(int k, int[] nums) {
        this.k = k;
        for (int i : nums) {
            if (minHeap.isEmpty())
                minHeap.offer(i);
            else {
                if (k > minHeap.size() || i >= minHeap.peek())
                    minHeap.offer(i);
                if (k < minHeap.size())
                    minHeap.poll();
            }
        }
    }
    public int add(int val) {
        if (k > minHeap.size() || val >= minHeap.peek())
            minHeap.offer(val);
        if (k < minHeap.size())
            minHeap.poll();

        return minHeap.peek();
    }
}
